According to some business data models, an order consists of several activities which must be performed to complete, fulfill, and/or satisfy the order. Scheduling applications may be used to schedule the performance of the activities of an order.
An activity may be scheduled by “placing” the activity on a resource that is capable of executing the activity. Placing the activity may consist of assigning the activity to the resource in association with a defined start time, a defined duration and a defined end time. The placed activity is therefore intended to consume some of the capacity offered by the resource between the start time and the end time.
The placed activity may consume the capacity of another resource during the same time interval. Such capacity is known as a secondary capacity requirement of the activity. Some activities are sequence-dependent, in that their duration depends on the preceding activity on the same resource. Accordingly, the duration, and hence the start time or end time, of a sequence-dependent activity may change during the scheduling process.
The foregoing elements may complicate the scheduling (or rescheduling) of orders and their constituent activities. For example, the activities of an order might be moved to fall in a time slot where required resource capacity is available. An unmoved sequence-dependent activity may increase in duration if one of the moved activities is on the same resource as the sequence-dependent activity. Accordingly, the sequence-dependent activity may overlap the moved activity in time.
FIGS. 1A and 1B provide one example of the foregoing. As shown, primary resources R1, R2 and R3 are primary resources and SR represents a main secondary resource. Order 1 consists of production activities A101, A201, and A301, and corresponding sequence-dependent setup activities S101, S201, and S301, whose durations depend on a current predecessor activity on their corresponding resources.
Similarly, order 2 consists of production activity A102 and sequence-dependent setup activity S102, production activity A202 and sequence-dependent setup activity S202, and production activity A302 and sequence-dependent setup activity S302. During the activities of each order, SR is occupied by production activity A10 on R1 and setup activities S20 and S30 on resource R2 and R3.
FIG. 1A illustrates a scenario in which secondary capacity requirements of a single secondary resource are consumed by activities placed on different primary resources. Moreover, the vertical lines between the production activities on R1 and R2 and R2 and R3 represent time constraints specifying a minimum distance of 0 seconds and a maximum distance of 1 second.
Upon reviewing the schedule of FIG. 1A, a scheduler may wish to move order 1 somewhat to the right (i.e., later in time), using backward scheduling. The intention of such a move is to close the gap between both orders on secondary resource SR.
More particularly, all activities of order 1 are removed from the board, which causes the sequence-dependent setup activities of order 2 to change in duration. The present example assumes that the durations decrease. A101 is the first activity to be re-placed and will be moved right to fill the desired slot, as shown in FIG. 1B. This placement changes the duration of S102. S101 and A201 are the next activities to be placed, which causes S202 to change, so S202, A302 and S302 are removed. S202 is again placed without overlap, as are A302 and S302.
Next, upon placing A301 as shown, it is recognized that sequence-dependent setup activity S302 cannot change its duration in response. In other words, the placement of A301 must cause S302 to become longer, but such a lengthening would result in the illustrated overlap with A101. A301 therefore cannot find a valid slot and an error is issued (e.g., no slot found).
Approaches are desired for efficiently scheduling activities on resources. Such approaches may address issues arising as a result of sequence-dependent setup activities and/or activities belonging to different primary resources and having closely-related finite capacity requirements on a common secondary resource.